package datastructure.unionfind;

/**
 * 基于size的优化 在合并的时候，判断将数量少的指向数量多的元素跟节点
 */
public class UnionFind3 implements UF {

    //实际表示parent[i]指向那个节点
    private int[] parent;
    //维护每一个元素节点有多少个元素指向,以i为跟的元素个数统计
    private int[] size;

    public UnionFind3(int size) {
        parent = new int[size];
        this.size = new int[size];
        //初始的时候，parent[i]=i  指向自己
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            this.size[i] = 1;
        }
    }

    @Override
    public int getSize() {

        return parent.length;
    }

    // 查看元素p对饮的集合编号  O(h) h为树的高度
    // parent[i]表示第i个元素指向那个节点
    // 向上查找，直到查到跟节点
    private int find(int p) {
        if (p < 0 || p >= parent.length)
            throw new IllegalArgumentException("p is out of bound.");
        while (p != parent[p]) {
            p = parent[p];
        }

        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        // 复杂度分析 查找 logn
        int findP = find(p);
        int findQ = find(q);
        return findP == findQ;
    }


    @Override
    public void unionElements(int p, int q) {
        int parentP = find(p);
        int parentQ = find(q);
        if (parentP == parentQ) {
            return;
        } else {

            //在合并的时候判断哪一个跟节点指向元素多
            //p >q q指向p的跟节点
            if (size[parentP] > size[parentQ]) {
                parent[parentQ] = parentP;
                size[parentQ] += size[parentP];
            } else {// p <= q  p指向q
                parent[parentP] = parentQ;
                size[parentP] += size[parentQ];
            }
        }
    }

}
